#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

#define MAX_GUARD INT_MAX
typedef struct MAXHEAP Heap;
typedef int ElementType;
struct MAXHEAP {
	ElementType *Data;
	int Capacity;
	int Size;
};
Heap *HeapInit(int capacity);
_Bool HeapFull(Heap*);
_Bool HeapEmpty(Heap*);
void Ins(Heap*,ElementType);
ElementType Del(Heap*);
void BuildHeap(Heap*,int *,int);
void PrtHeap(Heap*);
int main(){
	int a[]={1,3,5,99,67,30,44,50,11};
	Heap *h=HeapInit(100);
	BuildHeap(h,a,sizeof(a)/sizeof(int));
	PrtHeap(h);
	return 0;
}

Heap *HeapInit(int capacity){
	Heap *h=malloc(sizeof(Heap));
	h->Data=malloc(sizeof(ElementType)*(capacity+1));
	h->Data[0]=MAX_GUARD;
	h->Capacity=capacity;
	h->Size=0;
	return h;
}
void Ins(Heap *h,ElementType x){
	//h->Data[++h->Size]=x;
	int current=++h->Size;
	if( h->Size > h->Capacity ) return;
	int father=current/2;
	for( ; h->Data[father] < x ; current=father,father=current/2 ){
		h->Data[current]=h->Data[father];
	}
	h->Data[current]=x;
	return;
}
ElementType Del(Heap *h){
	ElementType r=h->Data[1];
	ElementType e=h->Data[h->Size--];
	int current=1,s=h->Size,child=2*current;
	for( ; child <= s ; current=child,child=2*current ){
		if( child < s && h->Data[child] < h->Data[child+1] )
			child++;
		if( h->Data[child] > e )
			h->Data[current]=h->Data[child];
		else
			break;
	}
	h->Data[current]=e;
	return r;
}
void BuildHeap(Heap *h,int *arr,int n){
	if( n > h->Capacity )return;
	int current;
	int child;
	ElementType e;
	memcpy(&h->Data[1],arr,sizeof(int)*n);
	h->Size=n;
	for( int c=h->Size/2; c >= 0 ; c-- ){
		for( current=c,child=2*current,e=h->Data[current] ; child <= h->Size ; current=child,child=2*current ){
			if( child < h->Size && h->Data[child] < h->Data[child+1] )
				child++;
			if( h->Data[child] > e )
				h->Data[current]=h->Data[child];
			else
				break;
		}
		h->Data[current]=e;
	}
	return;
}
void PrtHeap(Heap *h){
	printf("\n");
	for(int i=1;i<=h->Size;i++)
		printf("%4d",h->Data[i]);
	printf("\n");
}
